__author__ = 'pcJxy'

import random

prime_bases = [2, 3, 5, 7, 11, 13, 17, 19]


def gen_prime(bit_width=1024):
    """
    Generate a prime number with the specified bit width.

    :param bit_width:
    :return: a prime number.
    """
    prime_num_candidate = 0
    for i in range(bit_width):
        prime_num_candidate = prime_num_candidate * 2 + random.randint(0, 1)
    while not is_prime(prime_num_candidate):
        prime_num_candidate = prime_num_candidate + 1
    return prime_num_candidate


def is_prime(n: int) -> bool:
    """
    Check if a number is a prime number by invoking Miller Rabin judgement
    several times to get maximum correctness.

    :param n: the number to be judged.
    :return: if `n` is a prime number.
    """
    for base in prime_bases:
        if not miller_rabin(n, base): return False
    return True


def miller_rabin(n: int, base: int) -> bool:
    """
    Miller Rabin algorithm, a prime number judgement.

    :param base: judgement base number.
    :param n: the number to be judged.
    :return: if `n` is a prime number.
    """
    # Filter out prime less than 3.
    if n == 1: return False
    if n == 2: return True
    if n % 2 == 0: return False
    m, k, = n - 1, 0
    # # We will divide `m` by `2` from `n - 1`, until it becomes an odd number.
    while m % 2 == 0:
        m, k = m // 2, k + 1
    x = pow(base, m, n)
    if x == 1 or x == n - 1: return True
    while k > 1:
        x = pow(x, 2, n)
        if x == 1: return False
        if x == n - 1: return True
        k = k - 1
    return False
